package array;

import java.util.*;

public class leetCode40_combinationSum2 {

    public static void main(String[] args) {
        leetCode40_combinationSum2 a = new leetCode40_combinationSum2();
        int[] candidates = {10,1,2,7,6,1,5};
        int target = 8;
        a.combinationSum22(candidates,target);
    }

    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<Integer> trace = new ArrayList<>();
        Arrays.sort(candidates);
        build(candidates,0,target,trace,0);
        return res;
    }

    public void build(int[] candidates, int sum, int target,List<Integer> trace,int start){
        if(sum == target){
            res.add(new ArrayList<>(trace));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            if(i > start && candidates[i] == candidates[i - 1]){
                continue;
            }
            if(sum + candidates[i] <= target){
                trace.add(candidates[i]);
                build(candidates,sum + candidates[i],target,trace,i + 1);
                trace.remove(trace.size() - 1);
            }else{
                break;
            }
        }
    }

    List<List<Integer>> res2 = new ArrayList<>();
    public List<List<Integer>> combinationSum22(int[] candidates, int target) {
        if(candidates == null || candidates.length == 0){
            return res2;
        }
        Arrays.sort(candidates);
        List<Integer> trace = new ArrayList<>();
        build2(candidates,trace,0,0,target);
        return res2;

    }

    public void build2(int[] candidates,List<Integer> trace,int sum,int index,int target){
        if(sum == target){
            res2.add(new ArrayList<>(trace));
            return;
        }

        for (int i = index; i < candidates.length; i++) {
            if(i > index && candidates[i] == candidates[i - 1]){
                continue;
            }
            if(sum + candidates[i] <= target){
                trace.add(candidates[i]);
                build2(candidates, trace, sum + candidates[i], i + 1, target);
                trace.remove(trace.size() - 1);
            }else{
                break;
            }
        }


    }


}
